package lc2;

import org.junit.Test;

public class Ex679 {
    class Solution {
        public boolean judgePoint24(int[] cards) {
            int n = cards.length;
            double[] nums = new double[n];
            for (int i = 0; i < n; i++) {
                nums[i] = cards[i];
            }
            return calc(nums);
        }
    
        private static final double MIN = 1e-6;
        private static final double TARGET = 24;
        private boolean calc(double[] nums) {
            int n = nums.length;
            if (n == 1) {
                return isEqual(nums[0], TARGET);
            }
    
            for (int i = 0; i < n; i++) { 
                for (int j = 0; j < n; j++) {
                    if (i == j) {
                        continue;
                    }
                    //挑两个数做运算，剩下的复制到新数组
                    double[] tmp = new double[n - 1];
                    int idx = 0;
                    for (int k = 0; k < n; k++) {
                        if (k != i && k != j) {
                            tmp[idx++] = nums[k];
                        }
                    }
                    tmp[idx] = nums[i] + nums[j];
                    if (calc(tmp)) {
                        return true;
                    }
                    tmp[idx] = nums[i] - nums[j];
                    if (calc(tmp)) {
                        return true;
                    }
                    tmp[idx] = nums[j] - nums[i];
                    if (calc(tmp)) {
                        return true;
                    }
                    tmp[idx] = nums[i] * nums[j];
                    if (calc(tmp)) {
                        return true;
                    }
                    tmp[idx] = nums[i] / nums[j];
                    if (calc(tmp)) {
                        return true;
                    }
                    tmp[idx] = nums[j] / nums[i];
                    if (calc(tmp)) {
                        return true;
                    }
                }
            }
            return false;
        }
    
        private boolean isEqual(double a, double b) {
            return Math.abs(a - b) < MIN;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{1,2,1,2};
        System.out.println(s.judgePoint24(nums));
    }
}
